2A
弱智题,硬判即可。
Code
#include <cstdio>
#include <cstring>
char s[55];
int cnt1, cnt2, n, len, flag;
int main() {
scanf("%d%s", &n, s + 1);
len = strlen(s + 1);
for (int i = 1; i <= len / 2; i++) {
if (s[i] != '4' && s[i] != '7') flag = 1;
else cnt1 += s[i] - '0';
}
for (int i = len / 2 + 1; i <= len; i++) {
if (s[i] != '4' && s[i] != '7') flag = 1;
else cnt2 += s[i] - '0';
}
if (cnt1 != cnt2 || flag) puts("NO");
else puts("YES");
return 0;
}
2B
注意到 ,所以上界为 ,暴力枚举即可。
Code
#include <cstdio>
#include <cmath>
bool check(int x) {
return x == 4 || x == 7;
}
int mask(int x) {
int c = 0, ret = 0;
for (; x; x /= 10) if (check(x % 10)) ret += x % 10 * pow(10, c++);
return ret;
}
int main() {
int a, b, c;
scanf("%d%d", &a, &b);
for (c = a + 1; c <= 177777; c++) if (mask(c) == b) break;
printf("%d\n", c);
return 0;
}
2C/1A
统计出所有 满足 ,个数记为 。所有 满足 ,个数记为 ,容易证明答案为
。
Code
#include <cstdio>
#include <cmath>
const int N = 1e5 + 5;
char a[N], b[N];
int n, cnt1, cnt2;
inline int min(int x, int y) {
return x < y ? x : y;
}
int main() {
scanf("%s%s", a + 1, b + 1);
for (int i = 1; a[i]; i++) {
if (a[i] == '4' && b[i] == '7') cnt1++;
if (a[i] == '7' && b[i] == '4') cnt2++;
}
printf("%d\n", min(cnt1, cnt2) + abs(cnt1 - cnt2));
return 0;
}
2D/1B
注意到 和 的个数至多差 ,于是考虑先把 和 交替排列,再把剩余的字符插入序列。
容易发现在交替排列之后,插入字符一定存在不会影响 和 个数的方案。
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
int ans[N], a[5];
int main() {
cin >> a[1] >> a[2] >> a[3] >> a[4];
if (abs(a[3] - a[4]) > 1 ||
a[1] < a[3] || a[2] < a[3] ||
a[1] < a[4] || a[2] < a[4]) puts("-1"), exit(0);
int u = a[1], v = a[2], s = a[3], t = a[4], n = 1, flag = 0;
ans[1] = 4, u--;
while (s > 0 || t > 0) {
n++;
if (flag == 0) ans[n] = 7, v--, s--;
else ans[n] = 4, u--, t--;
flag ^= 1;
}
if (u < 0 || v < 0 || s < 0 || t < 0) {
u = a[1], v = a[2], s = a[3], t = a[4], n = 1, flag = 1;
ans[1] = 7, v--;
while (s > 0 || t > 0) {
n++;
if (flag == 0) ans[n] = 7, v--, s--;
else ans[n] = 4, u--, t--;
flag ^= 1;
}
if (u < 0 || v < 0) puts("-1"), exit(0);
putchar('7');
for (int i = 1; i <= u; i++) putchar('4');
if (ans[n] == 7) {
for (int i = 2; i <= n; i++) putchar(ans[i] + '0');
for (int i = 1; i <= v; i++) putchar('7');
} else {
for (int i = 2; i < n; i++) putchar(ans[i] + '0');
for (int i = 1; i <= v; i++) putchar('7');
putchar('4');
}
} else {
for (int i = 1; i <= u + 1; i++) putchar('4');
if (ans[n] == 7) {
for (int i = 2; i <= n; i++) putchar(ans[i] + '0');
for (int i = 1; i <= v; i++) putchar('7');
} else {
for (int i = 2; i < n; i++) putchar(ans[i] + '0');
for (int i = 1; i <= v; i++) putchar('7');
putchar('4');
}
}
}
2E/1C
待补。
1D
待补。
1E
一眼数据结构题,考虑线段树维护四种信息:
-
区间 的最长不下降子序列。
-
区间 的最长不上升子序列。
-
区间 的数字 的个数。
-
区间 的数字 的个数。
区间合并的方式显然,时间复杂度 。
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 4e6 + 5;
char s[N], op[N];
struct SegmentTree {
int fr[N], sv[N], lazy[N], inc[N], dec[N];
// inc: 最长不下降子序列
// dec: 最长不上升子序列
#define ls(u) u << 1
#define rs(u) u << 1 | 1
inline void pushup(int rt) {
fr[rt] = fr[ls(rt)] + fr[rs(rt)];
sv[rt] = sv[ls(rt)] + sv[rs(rt)];
inc[rt] = max(inc[ls(rt)] + sv[rs(rt)], inc[rs(rt)] + fr[ls(rt)]);
dec[rt] = max(dec[ls(rt)] + fr[rs(rt)], dec[rs(rt)] + sv[ls(rt)]);
}
inline void spread(int rt) {
swap(fr[rt], sv[rt]);
swap(inc[rt], dec[rt]);
lazy[rt] ^= 1;
}
inline void pushdown(int rt) {
if (lazy[rt]) {
spread(ls(rt));
spread(rs(rt));
lazy[rt] = 0;
}
}
void build(int rt, int l, int r) {
if (l == r) {
inc[rt] = dec[rt] = 1;
s[l] == '4' ? fr[rt] = 1 : sv[rt] = 1;
return void();
}
int mid = (l + r) >> 1;
build(ls(rt), l, mid);
build(rs(rt), mid + 1, r);
pushup(rt);
}
void update(int rt, int l, int r, int x, int y) {
if (x <= l && r <= y) return spread(rt);
pushdown(rt);
int mid = (l + r) >> 1;
if (x <= mid) update(ls(rt), l, mid, x, y);
if (y > mid) update(rs(rt), mid + 1, r, x, y);
pushup(rt);
}
} seg;
int main() {
int n, m, l, r;
scanf("%d%d%s", &n, &m, s + 1);
for (seg.build(1, 1, n); m; m--) {
scanf("%s", op);
if (op[0] == 'c') printf("%d\n", seg.inc[1]);
if (op[0] == 's') scanf("%d%d", &l, &r), seg.update(1, 1, n, l, r);
}
return 0;
}